{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Perceptron POStagger\n",
    "\n",
    "In this assignment, you will need to treat postagging on one word as classification problem.\n",
    "The classifier we choose is the (simplest) perceptron model.\n",
    "You will need to a perceptron models that _classify on current window of words, along with previous POStag._\n",
    "\n",
    "You will need to implement the following parts:\n",
    "- mapping facility from feature string to its index in the parameter matrix W\n",
    "- perceptron update\n",
    "- calculate the score of given features and class\n",
    "- (part of) the feature extraction\n",
    "\n",
    "You should get an accuracy of more than **91.0** after the first round of training on the development set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from copy import copy\n",
    "\n",
    "class PerceptronClassifier(object):\n",
    "    # The perceptron classifier\n",
    "    def __init__(self, max_iter=10, training_data=None, devel_data=None):\n",
    "        '''\n",
    "        Parameters\n",
    "        ----------\n",
    "        max_iter: int\n",
    "            The max number of iteration\n",
    "        training_data: list\n",
    "            The training data\n",
    "        devel_data: list\n",
    "            The development data, to determine the best iteration.\n",
    "        '''\n",
    "        self.max_iter = max_iter\n",
    "        if training_data is not None:\n",
    "            self.fit(training_data, devel_data)\n",
    "\n",
    "            \n",
    "    def fit(self, training_data, devel_data=None):\n",
    "        '''\n",
    "        Estimate the parameters for perceptron model. For multi-class perceptron, parameters can be\n",
    "        treated as a T \\times D matrix W, where T is the number of labels and D is the number of\n",
    "        features.\n",
    "        '''\n",
    "        # feature_alphabet is a mapping from feature string to it's dimension in the feature space,\n",
    "        # e.g. feature_alphabet['U1=I']=3, which means 'U1=I' is in the third column of W\n",
    "        # \n",
    "        # W = [[ . . 1 . . .],\n",
    "        #      ...\n",
    "        #      [ . . 1 . . .]]\n",
    "        #            ^\n",
    "        #            |\n",
    "        #         'U1=I'\n",
    "        self.feature_alphabet = {'None': 0}\n",
    "        self.label_alphabet = {}\n",
    "\n",
    "        # Extract features, build the feature_alphabet, label_alphabet and training instance pairs.\n",
    "        # Each instance consist a tuple (X, Y) where X is the mapped features (list(int)), and Y is\n",
    "        # the index of the corresponding label.\n",
    "        instances = []\n",
    "        for words, tags in training_data:\n",
    "            L = len(words)\n",
    "            prev = '<s>'\n",
    "            for i in range(L):\n",
    "                # Your code here, extract features and give it into X, convert POStag to index and\n",
    "                # give it to Y\n",
    "                X = \n",
    "                Y = \n",
    "                instances.append((X, Y))\n",
    "\n",
    "        # Build a mapping from index to label string to recover POStags.\n",
    "        self.labels = [-1 for k in self.label_alphabet]\n",
    "        for k in self.label_alphabet:\n",
    "            self.labels[self.label_alphabet[k]] = k\n",
    "\n",
    "        self.D, self.T = len(self.feature_alphabet), len(self.label_alphabet)\n",
    "        print('number of features : %d' % self.D)\n",
    "        print('number of labels: %d' % self.T)\n",
    "\n",
    "        # Allocate the weight matrix W\n",
    "        self.W = [[0 for j in range(self.D)] for i in range(self.T)]\n",
    "        self.best_W = None\n",
    "        best_acc = None\n",
    "\n",
    "\n",
    "        for it in range(self.max_iter):\n",
    "            # The training part,\n",
    "            n_errors = 0\n",
    "            print('training iteration #%d' % it)\n",
    "            for X, Y in instances:\n",
    "                # Your code here, ake a prediction and give it to Z\n",
    "                Z = \n",
    "                if Z != Y:\n",
    "                    # Your code here. If the predict is incorrect, perform the perceptron update\n",
    "                    n_errors += 1\n",
    "                    for x in X:\n",
    "                        # The perceptron update part.\n",
    "\n",
    "            print('training error %d' % n_errors)\n",
    "\n",
    "            if devel_data is not None:\n",
    "                # Test accuracy on the development set if provided.\n",
    "                n_corr, n_total = 0, 0\n",
    "                for words, tags in devel_data:\n",
    "                    prev = '<s>'\n",
    "                    for i in range(len(words)):\n",
    "                        Z = self.predict(words, i, prev)\n",
    "                        Y = self.label_alphabet[tags[i]]\n",
    "                        if Z == Y:\n",
    "                            n_corr += 1\n",
    "                        n_total += 1\n",
    "                        prev = self.labels[Z]\n",
    "                print('accuracy: %f' % (float(n_corr)/n_total))\n",
    "                if best_acc < float(n_corr)/n_total:\n",
    "                    # If this round is better than before, save it.\n",
    "                    best_acc = float(n_corr)/n_total\n",
    "                    self.best_W = copy(self.W)\n",
    "                    \n",
    "        if self.best_W is None:\n",
    "            self.best_W = copy(self.W)\n",
    "\n",
    "            \n",
    "    def extract_features(self, words, i, prev_tag=None, add=True):\n",
    "        '''\n",
    "        Extract features from words and prev POS tag, if `add` is True, also insert the feature\n",
    "        string to the feature_alphabet.\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        words: list(str)\n",
    "            The words list  \n",
    "        i: int\n",
    "            The position\n",
    "        prev_tag: str\n",
    "            Previous POS tag\n",
    "        add: bool\n",
    "            If true, insert the feature to feature_alphabet.\n",
    "            \n",
    "        Return\n",
    "        ------\n",
    "        mapped_features: list(int)\n",
    "            The list of hashed features.\n",
    "        '''\n",
    "        L = len(words)\n",
    "        context = ['<s>' if i- 2 < 0 else words[i- 2],\n",
    "                   '<s>' if i- 1 < 0 else words[i- 1],\n",
    "                   words[i],\n",
    "                   '<e>' if i+ 1 >= L else words[i+ 1],\n",
    "                   '<e>' if i+ 2 >= L else words[i+ 1]]\n",
    "        raw_features = ['U1=%s' % context[0],\n",
    "                    'U2=%s' % context[1],\n",
    "                    'U3=%s' % context[2],\n",
    "                    'U4=%s' % context[3],\n",
    "                    'U5=%s' % context[4],\n",
    "                    'U1,2=%s/%s' % # Your code here, extract the bigram raw feature,\n",
    "                    'U2,3=%s/%s' % # Your code here, extract the bigram raw feature,\n",
    "                    'U3,4=%s/%s' % # Your code here, extract the bigram raw feature,\n",
    "                    'U4,5=%s/%s' % # Your code here, extract the bigram raw feature,\n",
    "                    ]\n",
    "        \n",
    "        if prev_tag is not None:\n",
    "            raw_features.append('B=%s' % prev_tag)\n",
    "\n",
    "        mapped_features = []\n",
    "        for f in raw_features:\n",
    "            if add and (f not in self.feature_alphabet):\n",
    "                # Your code here, insert the feature string to the feature_alphabet.\n",
    "                self.feature_alphabet[f] = \n",
    "            # Your code here, map the string feature to index.\n",
    "            \n",
    "            \n",
    "        return mapped_features\n",
    "\n",
    "    \n",
    "    def _score(self, features, t):\n",
    "        '''\n",
    "        Calcuate score from the given features and label t\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        features: list(int)\n",
    "            The hashed features\n",
    "        t: int\n",
    "            The index of label\n",
    "            \n",
    "        Return\n",
    "        ------\n",
    "        s: int\n",
    "            The score\n",
    "        '''\n",
    "        # Your code here, compute the score.\n",
    "        s= \n",
    "        return s\n",
    "\n",
    "    \n",
    "    def _predict(self, features):\n",
    "        '''\n",
    "        Calcuate score from the given features and label t\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        features: list(int)\n",
    "            The hashed features\n",
    "        t: int\n",
    "            The index of label\n",
    "            \n",
    "        Return\n",
    "        ------\n",
    "        best_y: int\n",
    "            The highest scored label's index\n",
    "        '''\n",
    "        pred_scores = [self._score(features, y) for y in range(self.T)]\n",
    "\n",
    "        best_score, best_y = None, None\n",
    "        # Your code here, find the highest scored class from pred_scores\n",
    "        \n",
    "        return best_y\n",
    "    \n",
    "    \n",
    "    def predict(self, words, i, prev_tag=None):\n",
    "        '''\n",
    "        Make prediction on list of words\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        words: list(str)\n",
    "            The words list  \n",
    "        i: int\n",
    "            The position\n",
    "        prev_tag: str\n",
    "            Previous POS tag\n",
    "        \n",
    "        Return\n",
    "        ------\n",
    "        y: int\n",
    "            The predicted label's index\n",
    "        '''\n",
    "        X = self.extract_features(words, i, prev_tag, False)\n",
    "        y = self._predict(X)\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def greedy_search(words, classifier):\n",
    "    '''\n",
    "    Perform greedy search on the classifier.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    words: list(str)\n",
    "        The word list\n",
    "    classifier: PerceptronClassifier\n",
    "        The classifier object.\n",
    "    '''\n",
    "    prev = '<s>'\n",
    "    ret=[]\n",
    "    for i in range(len(words)):\n",
    "        # Your code here, implement the greedy search,\n",
    "        label = \n",
    "        ret.append(label)\n",
    "        prev = ret[-1]\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from dataset import read_dataset\n",
    "\n",
    "train_dataset = read_dataset('./penn.train.pos.gz')\n",
    "devel_dataset = read_dataset('./penn.devel.pos.gz')\n",
    "\n",
    "print('%d is training sentences.' % len(train_dataset))\n",
    "print('%d is development sentences.' % len(devel_dataset))\n",
    "\n",
    "perceptron = PerceptronClassifier(max_iter=1, training_data=train_dataset, devel_data=devel_dataset)\n",
    "\n",
    "n_corr, n_total = 0, 0\n",
    "for devel_data in devel_dataset:\n",
    "    devel_data_x, devel_data_y = devel_data\n",
    "    pred_y = greedy_search(devel_data_x, perceptron)\n",
    "    for pred_tag, corr_tag in zip(pred_y, devel_data_y):\n",
    "        if pred_tag == corr_tag:\n",
    "            n_corr += 1\n",
    "        n_total += 1\n",
    "print(\"accuracy: %f\" % (float(n_corr)/ n_total))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print greedy_search(['HMM', 'is', 'a', 'widely', 'used', 'model', '.'], perceptron)\n",
    "print greedy_search(['I', 'like', 'cat', ',', 'but', 'I', 'hate', 'eating', 'fish', '.'], perceptron)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Work around the test dataset\n",
    "from __future__ import print_function\n",
    "\n",
    "test_dataset = read_dataset('./penn.test.pos.blind.gz')\n",
    "\n",
    "fpo=open('./penn.test.perceptron.pos.out', 'w')\n",
    "\n",
    "for test_data_x, test_data_y in test_dataset:\n",
    "    pred_y = greedy_search(test_data_x, hmm)\n",
    "    print(\" \".join(y for y in pred_y), file=fpo)\n",
    "\n",
    "fpo.close()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
